import { BinTree } from './BinTree'

const bt: BinTree = {
  val: 1,
  left: {
    val: 2,
    left: {
      val: 4,
      left: null,
      right: null,
    },
    right: {
      val: 5,
      left: null,
      right: null,
    },
  },
  right: {
    val: 3,
    left: {
      val: 6,
      left: null,
      right: null,
    },
    right: {
      val: 7,
      left: null,
      right: null,
    },
  },
}

/**
 * 后序遍历
 * @param root 根节点
 */
/* const postorder = (root: BinTree | null) => {
  if (!root) {
    return
  }
  postorder(root.left)
  postorder(root.right)
  console.log(root.val)
} */

const postorder = (root: BinTree | null) => {
  if (!root) {
    return
  }
  const outputStack: BinTree[] = []
  const stack: BinTree[] = [root]
  while (stack.length) {
    const n = stack.pop() as BinTree
    outputStack.push(n)
    if (n.left) {
      stack.push(n.left)
    }
    if (n.right) {
      stack.push(n.right)
    }
  }
  while (outputStack.length) {
    const n = outputStack.pop() as BinTree
    console.log(n.val)
  }
}

postorder(bt)
